//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
// Related Topics 栈 数组 单调栈 👍 1640 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

public class _84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        int[] heights = {2,1,5,6,2,3};
        Solution solution = new _84_LargestRectangleInHistogram().new Solution();
        System.out.println(solution.largestRectangleArea(heights));
    }

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) return 0;
        if (heights.length == 1) return heights[0];
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        int[] newHeight = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeight[i + 1] = heights[i];
        }
        newHeight[newHeight.length - 1] = 0;
        stack.addLast(newHeight[0]);
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[stack.peekLast()] > newHeight[i]) {
                int height = newHeight[stack.removeLast()];
                int width = i - stack.peekLast() - 1;

                max = Math.max(max, height * width);
            }
            stack.addLast(i);
        }

        return max;
    }
}
// 官方解法，没有使用哨兵
class Solution1 {
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) return 0;
        if (heights.length == 1) return heights[0];
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;

        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                int height = heights[stack.removeLast()];

                while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.removeLast();
                }

                int width = stack.isEmpty() ? i - (-1) - 1 : i - stack.peekLast() - 1;
//                    if (stack.isEmpty()) {
//                        width = i - (-1) - 1;
//                    } else {
//                        width = i - stack.peekLast() - 1;
//                    }
                max = Math.max(max, height * width);
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.removeLast()];

            while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                stack.removeLast();
            }

            int width = stack.isEmpty() ? heights.length : heights.length - stack.peekLast() - 1;
//                    if (stack.isEmpty()) {
//                        width = i - (-1) - 1;
//                    } else {
//                        width = i - stack.peekLast() - 1;
//                    }
            max = Math.max(max, height * width);
        }
        return max;
    }
}

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution2 {
        public int largestRectangleArea(int[] heights) {
            int len = heights.length;
            if (len == 0) {
                return 0;
            }
            if (len == 1) {
                return heights[0];
            }
            int area = 0;
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                    int height = heights[stack.removeLast()];

                    while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                        stack.removeLast();
                    }

                    int width;
                    if (stack.isEmpty()) {
                        width = i;
                    } else {
                        width = i - stack.peekLast() - 1;
                    }
                    area = Math.max(area, width * height);
                }
                stack.addLast(i);
            }
            while (!stack.isEmpty()) {
                int height = heights[stack.removeLast()];

                while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
                    stack.removeLast();
                }

                int width;
                if (stack.isEmpty()) {
                    width = len;
                } else {
                    width = len - stack.peekLast() - 1;
                }
                area = Math.max(area, width * height);
            }
            return area;
        }
        /**
         * 官方的暴力解法，比我的好，因为人家是从中间向两边，秒一点
         * @param heights
         * @return
         */
        public int largestRectangleArea_i(int[] heights) {
            int res = 0;
            for (int i = 0; i < heights.length; i++) {
                int height = heights[i];
                int left = i;
                int right = i;
                for (int j = i; j >= 0; j--) {
                    if (heights[j] >= height) {
                        left = j;
                    } else {
                        break;
                    }
                }
                for (int j = i; j < heights.length; j++) {
                    if (heights[j] >= height) {
                        right = j;
                    } else {
                        break;
                    }
                }
                int len = right - left + 1;
                res = res >= len * height ? res : len * height;
            }
            return res;
        }
        /**
         * 自己写的暴力解法
         * @param heights
         * @return
         */
        public int largestRectangleArea_baoli(int[] heights) {
            int res = 0;
            for (int i = 0; i < heights.length; i++) {
                for (int j = i; j < heights.length; j++) {
                    int min = getMin(heights, i, j);
//                    System.out.println("i:" + i + "-j:" + j + "->min:" + min);
                    int s = (j - i + 1) * min;
                    res = res < s ? s : res;
                }
            }
            return res;
        }

        private int getMin(int[] heights, int i, int j) {
            int min = heights[i];
            for (int k = i; k <= j; k++) {
                min = heights[k] < min ? heights[k] : min;
            }
            return min;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}